package com.leetcode.array;

/**
 * @author: ZhouBert
 * @date: 2019/10/17
 * @description: 33. 搜索旋转排序数组
 * B
 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 * ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
 * 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
 * 你可以假设数组中不存在重复的元素。
 * <p>
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * 示例 1:
 * 输入: nums = [4,5,6,7,0,1,2], target = 0
 * 输出: 4
 * 示例 2:
 * 输入: nums = [4,5,6,7,0,1,2], target = 3
 * 输出: -1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SearchinRotatedSortedArray33B {

	/**
	 * 我的思路：
	 * 1.找到反转的点i,nums[i-1]>nums[i]-->针对两个部分进行二分查找
	 * 	1 ms-93.83%
	 * todo:答案中有个取巧的办法，暂时先放着...
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int search(int[] nums, int target) {
		if (nums == null || nums.length == 0) {
			return -1;
		}
		int left = 0, right = nums.length - 1, mid = 0;
		if (nums[0] == target) {
			return 0;
		}
		boolean ifNeed = true;
		if (nums[left] < nums[right]) {
			ifNeed = false;
		} else if (nums[left] == nums[right]) {
			return nums[0] == target ? 0 : -1;
		}
		if (ifNeed) {
			///1.找到反转的点 mid
			while (left <= right) {
				mid = left + (right - left) / 2;
				///找到了，返回最小的点
				if (nums[mid + 1] < nums[mid]) {
					mid++;
					break;
				} else if (nums[left] < nums[mid]) {
					left = mid + 1;
				} else {
					right = mid;
				}
			}
///2.锁定区间在 mid~right
			if (nums[0] > target) {
				left = mid;
				right = nums.length - 1;
			}
			///3.锁定区间在 left+1~mid-1
			else {
				left = 1;
				right = mid - 1;
			}
		}


		while (left <= right) {
			mid = left + (right - left) / 2;
			///
			if (nums[mid] == target) {
				return mid;
			}
			if (nums[mid] > target) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] nums = new int[]{4, 5, 6, 7, 0, 1, 2};
		nums = new int[]{5, 1, 3};
		nums = new int[]{3, 4, 5, 6, 7, 1, 2};
		nums = new int[]{8, 9, 2, 3, 4};
		int target = 1;
		target = 4;
		target = 9;
		System.out.println(search(nums, target));
	}
}
